package com.congee02;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Set;

public class NthUglyNumber {

    // 排序 -> 优先队列 + hash
    public int nthUglyNumber(int n) {

        int[] factors = new int[]{2, 3, 5};

        Set<Long> handled = new HashSet<>();

        PriorityQueue<Long> heap = new PriorityQueue<>();

        handled.add(1L);
        heap.offer(1L);

        int ans = 0;
        for (int i = 0 ; i < n ; i ++ ) {
            Long cur = heap.poll();
            ans = cur.intValue();
            for (int factor : factors) {
                long next = factor * cur;
                if (handled.add(next)) {
                    heap.offer(next);
                }
            }
        }

        return ans;
    }

}
